//最小的K个数
/*[4,5,1,6,2,7,3,8],4
        [1,2,3,4]*/

/*
import java.util.*;
public class Solution {
    */
/*
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
        *//*

    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        ArrayList<Integer> ret = new ArrayList<>();
        if(k==0) {
            return ret;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->{return b-a;});
        //创建大小为k的大根堆
        int i = 0;
        for( i = 0;i<k;i++) {
            maxHeap.offer(input[i]);
        }
        for(i = k;i<input.length;i++) {
            int peek = maxHeap.peek();
            if(peek >= input[i]) {
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        return new ArrayList<>(maxHeap);
    }
}
*/

/*
数组中的第K个最大元素
        [4,5,1,6,2,7,3,8],4
        [1,2,3,4]*/
/*
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }
    int qsort(int[] nums,int l,int r,int k) {
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left =  l- 1, right = r + 1 , i = l;
        //划分区域
        while(i < right) {
            if(nums[i]<key) {
                swap(nums,++left,i++);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(nums,--right,i);
            }
        }
        //[l,left],[left+1,rigth-1],[right,r]
        //进行核对
        int c = r-right+1 , b =right-left-1;
        if(c>=k) {
            return qsort(nums,right,r,k);
        } else if(b+c>=k) {
            return key;
        }else {
            return qsort(nums,l,left,k-b-c);
        }
    }
    void swap(int[] nums,int l,int r) {
        int tem = nums[l];
        nums[l] = nums[r];
        nums[r] = tem;
    }
}*/
